A computer network includes a collection of interconnected computing devices that exchange data and share resources. The devices may include, for example, web servers, database servers, file servers, routers, printers, end-user computers and other devices. The variety of devices may execute a myriad of different services and communication protocols. Each of the different services and communication protocols exposes the network to different security vulnerabilities. The physical interconnection of computing devices in a network is referred to as the “network topology.” Various situations exist in which discovery of the network topology by one or more of the computing devices of a network is useful or required.
For example, network management and performance analysis of layer two (L2) networks (e.g., large bridged-Ethernet networks) often require accurate topology information. This typically involves a management device identifying any connections between two L2 switches, i.e., so called switch-to-switch links, by interrogating (MAC) address forwarding tables within the devices. However, conventional techniques for discovering switch-to-switch links of a large L2 computer network often utilize significant computational resources. One conventional technique requires the management device to iterate over each media access control (MAC) address of each address forwarding table of each port of each L2 device within the network. In particular, the management device processes the MAC addresses to determine whether two other switches have at least three MAC addresses in common in their address forwarding tables (AFTs), determining which ports of each switch include three MAC addresses in common, and checking whether the three MAC addresses are found collectively on two ports of one switch and three ports of the other switch. When these criteria are met, the management device determines that a switch-to-switch link exists within the network. However, for n MAC addresses, the timing function for this technique is O(n3). That is, in the worst case, this technique requires approximately n3 mathematical operations to determine a link between the two switches. This technique is thus highly CPU-intensive and highly time consuming. Further details of the technique are described in “Topology Discovery for Large Ethernet Networks” by Bruce Lowekamp, David R. O'Hallaron, Thomas R. Gross; SIGCOMM'01, Aug. 27-31, 2001, the entire contents of which are incorporated by reference.